import math
from collections import Counter
import random


# 函数功能：从指定路径加载Wine数据集，对数据进行预处理，去除空行并将每行数据转换为特征-标签对的形式，最终返回处理后的数据集
# 参数说明：
# - file_path (str, 可选)：数据集文件的路径，默认为 'wine.data'，可根据实际情况指定不同路径
# 返回值说明：
# - 如果数据加载和预处理成功，返回一个包含特征-标签对的列表，每个元素为一个元组，元组的第一个元素是特征列表，第二个元素是对应的标签字符串；
# - 如果加载过程中出现文件未找到或数据格式错误等问题，返回空列表，并打印相应错误信息
def load_wine_data(file_path='wine.data'):
    data = []
    try:
        with open(file_path, 'r') as f:
            lines = f.readlines()  # 一次性读取文件中的所有行，返回一个字符串列表
            for line in lines:
                stripped_line = line.strip()  # 去除每行字符串两端的空白字符（如换行符、空格等）
                if stripped_line:  # 如果处理后的行不为空字符串，则表示该行包含有效数据
                    row = stripped_line.split(',')  # 以逗号为分隔符将字符串拆分成列表，得到每行数据的各个字段
                    label = row[0]  # 取每行数据的第一个字段作为类别标签
                    features = [float(x) for x in row[1:]]  # 使用列表推导式将除第一个字段（类别）之外的所有字段转换为浮点数，作为特征值
                    data.append((features, label))  # 将特征列表和标签组成元组，添加到数据列表中
    except FileNotFoundError:
        print(f"Error: 文件 {file_path} 未找到，请检查文件路径。")
    except ValueError:
        print("Error: 文件中存在无法转换为浮点数的值，请检查数据格式。")
    return data


# 函数功能：计算给定标签列表的信息熵，用于衡量数据集的混乱程度或不确定性
# 参数说明：
# - labels (list)：一个包含标签的列表，每个标签表示数据集中一个样本的类别
# 返回值说明：
# - 返回一个浮点数，表示计算得到的信息熵值，信息熵值越大，数据集的不确定性越高
def entropy(labels):
    total = len(labels)  # 计算标签列表中的样本总数
    counts = Counter(labels)  # 使用Counter类统计每个标签在列表中出现的次数，返回一个字典，键为标签，值为出现次数
    # 使用生成器表达式计算每个标签的概率乘以其对数概率的负值之和，得到信息熵
    # 概率计算为每个标签的出现次数除以总样本数，对数以2为底，用于衡量信息的不确定性
    return -sum((count / total) * math.log2(count / total) for count in counts.values())


# 函数功能：根据给定的特征索引和阈值，将数据集划分为两个子集，一个子集包含特征值小于等于阈值的样本，另一个子集包含特征值大于阈值的样本
# 参数说明：
# - data (list of tuples)：数据集，每个元素是一个包含特征列表和标签的元组，用于划分操作
# - feature_index (int)：一个整数，表示用于划分数据集的特征在特征列表中的索引位置
# - threshold (float)：一个浮点数，作为划分数据集的阈值，用于比较特征值
# 返回值说明：
# - 返回一个包含两个子集的元组，第一个子集包含特征值小于等于阈值的样本，第二个子集包含特征值大于阈值的样本，每个子集也是特征-标签对的列表
def split_dataset(data, feature_index, threshold):
    left, right = [], []  # 初始化两个空列表，用于存储划分后的子集
    for features, label in data:  # 遍历数据集中的每个样本
        if features[feature_index] <= threshold:  # 如果样本的指定特征值小于等于阈值
            left.append((features, label))  # 将该样本添加到左子集中
        else:
            right.append((features, label))  # 否则将该样本添加到右子集中
    return left, right  # 返回划分后的两个子集


# 函数功能：计算在给定特征和阈值下对数据集进行划分所获得的信息增益，信息增益用于评估特征对分类的重要性
# 参数说明：
# - data (list of tuples)：数据集，每个元素是一个包含特征列表和标签的元组，用于计算信息增益
# - feature_index (int)：一个整数，表示用于计算信息增益的特征在特征列表中的索引位置
# - threshold (float)：一个浮点数，作为划分数据集的阈值，用于比较特征值
# 返回值说明：
# - 返回一个浮点数，表示计算得到的信息增益值，信息增益值越大，说明使用该特征和阈值进行划分对分类越有帮助
def information_gain(data, feature_index, threshold):
    total_entropy = entropy([label for _, label in data])  # 计算原始数据集的信息熵
    left, right = split_dataset(data, feature_index, threshold)  # 根据给定特征和阈值划分数据集为左右子集
    p_left = len(left) / len(data) if data else 0  # 计算左子集在原始数据集中所占的比例，如果数据集为空则比例为0
    p_right = len(right) / len(data) if data else 0  # 计算右子集在原始数据集中所占的比例，如果数据集为空则比例为0
    # 计算信息增益，公式为原始数据集的信息熵减去划分后左右子集的信息熵加权和，权重为子集在原始数据集中的比例
    gain = total_entropy - (p_left * entropy([label for _, label in left]) +
                            p_right * entropy([label for _, label in right]))
    return gain


# 函数功能：递归地构建决策树，根据数据集的特征和标签，选择最佳的特征和阈值进行划分，直到满足停止条件
# 参数说明：
# - data (list of tuples)：当前用于构建决策树的数据集，每个元素是一个包含特征列表和标签的元组
# - available_features (set)：一个集合，包含当前可用作分裂的特征索引，用于控制决策树的构建过程
# 返回值说明：
# - 返回一个决策树节点，节点可以是一个字典，表示内部节点，包含特征索引、阈值、左右子树等信息；也可以是一个字符串，表示叶子节点，即类别标签
def build_tree(data, available_features):
    labels = [label for _, label in data]  # 提取数据集中所有样本的标签，组成一个标签列表

    # 如果数据集中所有样本的标签相同，说明已经到达叶子节点，返回该标签
    if len(set(labels)) == 1:
        return labels[0]

    # 如果没有可用的特征进行分裂，说明无法继续构建决策树，返回数据集中出现次数最多的类别标签
    if not available_features:
        return Counter(labels).most_common(1)[0][0]

    best_gain = -1  # 初始化最佳信息增益为 -1，用于记录找到的最大信息增益值
    best_feature = None  # 初始化最佳特征为 None，用于记录找到的最佳分裂特征的索引
    best_threshold = None  # 初始化最佳阈值为 None，用于记录找到的最佳分裂阈值

    # 遍历可用的特征，寻找最佳的分裂特征和阈值
    for feature_index in available_features:
        unique_values = set(sample[feature_index] for sample, _ in data)  # 获取当前特征的所有唯一值
        for value in unique_values:  # 遍历当前特征的每个唯一值，作为可能的分裂阈值
            gain = information_gain(data, feature_index, value)  # 计算使用当前特征和阈值进行划分的信息增益
            if gain > best_gain:  # 如果当前信息增益大于之前记录的最佳信息增益
                best_gain = gain  # 更新最佳信息增益
                best_feature = feature_index  # 更新最佳分裂特征索引
                best_threshold = value  # 更新最佳分裂阈值

    # 如果找到了有效的分裂（即最佳信息增益大于等于0），则根据最佳特征和阈值分裂数据集，并递归构建左右子树
    if best_gain >= 0:
        left, right = split_dataset(data, best_feature, best_threshold)  # 分裂数据集
        if not left or not right:  # 如果分裂后的某个子集为空，说明分裂无效，返回数据集中出现次数最多的类别标签
            return Counter(labels).most_common(1)[0][0]

        remaining_features = available_features.copy()  # 复制可用特征集合，用于构建子树时排除已使用的特征
        remaining_features.remove(best_feature)  # 从可用特征集合中移除当前使用的最佳特征

        return {
            'feature': best_feature,  # 决策树节点的特征索引
            'threshold': best_threshold,  # 决策树节点的分裂阈值
            'left': build_tree(left, remaining_features),  # 递归构建左子树
            'right': build_tree(right, remaining_features)  # 递归构建右子树
        }

    # 如果没有找到有效的分裂（即最佳信息增益小于0），返回数据集中出现次数最多的类别标签
    return Counter(labels).most_common(1)[0][0]


# 函数功能：使用构建好的决策树对给定样本进行分类，根据决策树的节点结构递归地判断样本的类别
# 参数说明：
# - tree (dict or str)：决策树节点或叶子节点标签，决策树的结构为嵌套字典，叶子节点为类别标签字符串
# - sample (list)：一个包含样本特征值的列表，与训练数据集中的特征顺序和维度一致
# 返回值说明：
# - 返回一个字符串，表示预测的样本类别标签
def classify(tree, sample):
    if isinstance(tree, str):  # 如果当前节点是叶子节点（即类别标签字符串）
        return tree  # 直接返回类别标签
    feature = tree['feature']  # 获取决策树节点的特征索引
    threshold = tree['threshold']  # 获取决策树节点的分裂阈值
    if sample[feature] <= threshold:  # 如果样本的特征值小于等于分裂阈值
        return classify(tree['left'], sample)  # 递归地在左子树中继续分类
    else:
        return classify(tree['right'], sample)  # 否则递归地在右子树中继续分类


if __name__ == "__main__":
    # 加载Wine数据集
    data = load_wine_data()
    if not data:
        print("数据加载失败，程序终止。")
    else:
        # 随机打乱数据集
        random.shuffle(data)
        split_index = int(len(data) * 0.8)  # 计算训练集和测试集的划分索引，80%的数据作为训练集
        train_data, test_data = data[:split_index], data[split_index:]  # 划分训练集和测试集

        # 确定可用的特征索引集合，范围为数据集中特征的数量
        features = set(range(len(data[0][0])))

        # 构建决策树
        tree = build_tree(train_data, features)

        # 测试决策树的分类准确性
        correct_predictions = sum(classify(tree, features) == label for features, label in test_data)  # 使用生成器表达式计算预测正确的样本数
        accuracy = correct_predictions / len(test_data)  # 计算分类准确率
        print(f"决策树分类准确率: {accuracy * 100:.2f}%")